package com.mj.listen2._01_排序.cmp;

/**
 * 快速排序
 *
 * @param <T>
 */
public class _07_QuickSort2<T extends Comparable<T>> extends Sort<T> {
    @Override
    protected void sort() {
        sort(0, array.length);
    }

    /**
     * 对 [begin,end) 内的数据进行快速排序
     *
     * @param begin
     * @param end
     */
    private void sort(int begin, int end) {
        if (end - begin < 2) {
            return;
        }
        // 找到轴点
        int pivotIndex = pivotIndex(begin, end);

        // 对左边孩子进行快速排序
        sort(begin, pivotIndex);

        // 对右边孩子进行快速排序
        sort(pivotIndex + 1, end);
    }

    /**
     * 构造出 [begin, end) 范围的轴点元素
     *
     * @param begin
     * @param end
     * @return
     */
    private int pivotIndex(int begin, int end) {
        // 参照物，最终会作为轴点元素
        T value = array[begin];
        // end指向最后一个元素
        end--;

        while (begin < end) {
            while (begin < end) {
                // 从后往前找
                if (cmp(array[end], value) > 0) {// end指针指向的位置元素大于轴点元素
                    // 直接向左移动指针
                    end--;
                } else {// end指针指向的位置元素小于等于轴点元素
                    // 需要把end位置的元素放置到左边去
                    array[begin++] = array[end];// 注意 end 指针不移动
                    break;
                }
            }

            while (begin < end) {
                // 从前往后找
                if (cmp(array[begin], value) < 0) {// begin指针指向的位置元素小于轴点元素
                    // 直接向右移动指针
                    begin++;
                } else {// begin 指针指向的位置元素大于等于轴点元素
                    // 需要把 begin 位置的元素放置到右边去
                    array[end--] = array[begin];
                    break;
                }
            }
        }

        // 将轴点元素放入最终的位置
        array[begin] = value;
        // 返回轴点元素的位置
        return begin;// begin == end
    }
}
